/*
 * MCR.cpp
 *
 *  Created on: Sep 19, 2011
 *      Author: correa
 */
/*******************************************************************************************************************************
 * Solving the maximum stable set problem using the algorithm described in
 *
 * E. Tomita and T. Kameda
 * An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
 * Journal of Global Optimization, 2007, 37:1, pages 95--111
 * http://dx.doi.org/10.1007/s10898-006-9039-7
 *
 * Parallel
 * --------
 *
 * A parallel (pthread based) version is obtained compiling it with _PT_PARALLEL_ defined
 *
 * Parallel parameters:
 *
 * 1) number of threads
 *
 * Distributed
 * -----------
 *
 * A distributed (MPI based) version is obtained compiling it with _PD_DISTRIBUTED_ (pulse-driven model)
 * or _ED_DISTRIBUTED_ (event-driven model) defined
 *
 * Distributed parameters:
 *
 * 1) number of donation attempts before locally terminating (#define ATTEMPTS)
 *
 * Termination:
 *
 * currently, a simplified termination detection mechanism is used. A fixed binary termination tree is determined and used
 * to propagate termination waves. In the event driven model, this same tree is used to start the computation as a
 * diffusing computation (in the sense of Dijkstra's termination algorithm).
 *
 */

#include <iostream>
#include <time.h>
#include <assert.h>

#include "StabSolvers.h"
#include "MCR.h"
#include <repository.h>
#include <Graph.h>
#include <sys/time.h>
#include <sys/resource.h>

template<>
int BackTrack<subproblem>::solveByEnumeration() {
	subproblem* current = sg->root();
	//if(current == NULL) printf("problemas com current \n");

	nnodes = 1;
	subproblem** subpqueue = (subproblem**)calloc(current->r*sg->numThreads(), sizeof(subproblem*));//every node has nt suns
	int q = 0;
	while (q >= 0) {
		//printf(" NOVO Q = %d P = %d \n",q, current->p);
		//fflush(NULL);

		//generate new subproblems
		if(current->p >= 0)subpqueue[q++] = current;
		//printf("vou chamar a generate() \n");
		//fflush(NULL);
		sg->generate(current, subpqueue, &q, &nnodes);

		q--;
		if (q >= 0)
			current = subpqueue[q];  // backtracking
	}

	qmax = sg->getBest();
	delete sg;

	return 0;
}

template<>
int BackTrack<subproblem>::getBest(double* val){
	*val = (int)qmax;
	return (int)qmax;
}

template<>
int BackTrack<subproblem>::getNodes(int* nnd){
	*nnd = (int)nnodes;
	return *nnd;
}

